//给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以
//决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。 
//
// 注意，删除一个元素后，子数组 不能为空。 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [1,-2,0,3]
//输出：4
//解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。 
//
// 示例 2： 
//
// 
//输入：arr = [1,-2,-2,3]
//输出：3
//解释：我们直接选出 [3]，这就是最大和。
// 
//
// 示例 3： 
//
// 
//输入：arr = [-1,-1,-1,-1]
//输出：-1
//解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
//     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
// 
//
// 
//
// 提示： 
// 
//
// 
// 1 <= arr.length <= 10⁵ 
// -10⁴ <= arr[i] <= 10⁴ 
// 
//
// Related Topics 数组 动态规划 👍 342 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-07-21 16:20:50
 * @description 1186.删除一次得到子数组最大和
 */
public class MaximumSubarraySumWithOneDeletion{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MaximumSubarraySumWithOneDeletion fun=new MaximumSubarraySumWithOneDeletion();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	private int[] arr;
	private int[][] memo;

	/**
	* arr是原数组，dfs(i,j)代表右端点下标是i，j=1是删除，j=0是不删除，子数组的最大值
	 * 如果j=0,不考虑i左边的数，那么dfs(i,0)=arr[i]，如果考虑i左边的数，那么dfs(i,0)=dfs(i-1,0)+arr[i]
	 *如果J=1,不删除i，那么dfs(i,1)=dfs(i-1,1)+arr[i]，如果删除i，那么dfs(i,1)=dfs(i-1,0)
	 * 取最大值,dfs(i,j)
	 * dfs(i,0)=Math.max(dfs(i-1,0),0)+arr[i]
	 * dfs(i,1)=Math.max(dfs(i-1,1)+arr[i],dfs(i-1,0))
	 * memo记忆化搜索保存递归到的值
	* */
	public int maximumSum(int[] arr) {
		this.arr = arr;
		int n = arr.length;
		int ans = Integer.MIN_VALUE;
		memo = new int[n][2];
		for (int[] row : memo)
			Arrays.fill(row, Integer.MIN_VALUE);
		for (int i = 0; i < n; i++)
			ans = Math.max(ans, Math.max(dfs(i, 0), dfs(i, 1)));
		return ans;
	}

	private int dfs(int i, int j) {
		if (i < 0) return Integer.MIN_VALUE / 2; // 除 2 防止负数相加溢出
		if (memo[i][j] != Integer.MIN_VALUE) return memo[i][j]; // 之前计算过
		if (j == 0) return memo[i][j] = Math.max(dfs(i - 1, 0), 0) + arr[i];
		return memo[i][j] = Math.max(dfs(i - 1, 1) + arr[i], dfs(i - 1, 0));
	}
	/*翻译成递推*/
	public int maximumSum1(int[] arr) {
		int n = arr.length;
		int ans = Integer.MIN_VALUE;
		//在0号加一位，从右往左递推用来表示边界
		int[][] f = new int[n + 1][2];
		Arrays.fill(f[0], Integer.MIN_VALUE / 2); // 除 2 防止负数相加溢出
		for (int i = 0; i < n; i++) {
			f[i + 1][0] = Math.max(f[i][0], 0) + arr[i];
			f[i + 1][1] = Math.max(f[i][1] + arr[i], f[i][0]);
			ans = Math.max(ans, Math.max(f[i + 1][0], f[i + 1][1]));
		}
		return ans;
	}
	/*空间优化，每次只用到了f[i]即上一步的
	* 所以可以用两个变量表示
	* 但是需要先计算f1再计算f0
	* 不然f0已经更新了	*/
	public int maximumSum2(int[] arr) {
		int ans = Integer.MIN_VALUE / 2;
		int f0 = ans;
		int f1 = ans;
		for (int x : arr) {
			f1 = Math.max(f1 + x, f0);
			f0 = Math.max(f0, 0) + x;
			ans = Math.max(ans, Math.max(f0, f1));
		}
		return ans;
	}


}

//leetcode submit region end(Prohibit modification and deletion)

}
